1. Field of the Invention
The present invention relates to a document layout processing method for generating a specific layout structure on the basis of a generic layout structure and the content of a particular document to be laid out, and to a device for carrying out such a method.
2. Description of the Related Art
In recent years, it has been proposed to perform layout of a document (document processing) on the basis of the concept of a so-called structured document according to which one document is handled as a combination of a logical structure based on its sections and paragraphs and a layout structure which represents how the content of the document is to be actually arranged.
One example of document layout processing has recently been realized which is based on an office document architecture (hereinafter referred to as the "ODA") (ODA=ISO 8613: Information Process-Text and Office System-Office Document Architecture (ODA) and Interchange Format (1989)) which belongs to the system of OSI (Open System Interconnection) proposed by the ISO (International Standards Organization).
According to the ODA, one document has, in addition to its layout structure, a logical structure which represents a structure obtained by logically grasping sections, paragraphs and the like. The content of a particular document is linked to logical objects positioned at the lowest level of a specific logical structure. FIG. 6 shows the relation between the specific logical structure and the document content linked thereto. In FIG. 6, the upper and lower portions with respect to the chain line indicated by an arrow A correspond to the specific logical structure and the document content, respectively.
The ODA enables automatic layout processing which automatically generates a specific layout structure permitted by a generic layout structure, according to document contents linked to a specific logical structure, and links the specific logical structure to the specific layout structure via the document contents. To automatically generate the specific layout structure according to the document contents linked to the specific logical structure indicates a series of manipulations, for example, a process in which if a certain document content is not completely laid out in a subordinate structure of a certain page object, a new page object is automatically generated and the overflown document content is laid out in the new page object.
FIG. 7 shows an example of a structure in which a document corresponding to the specific logical structure shown in FIG. 6 is laid out. In FIG. 7, the upper portion with respect to the chain line indicated by the arrow A corresponds to the specific logical structure, while the lower portion with respect to the chain line indicated by an arrow B corresponds to the specific layout structure. The example of FIG. 7 shows a case where although the content of Paragraph 2.1 of Section 2 is to be laid out on a first page, the content is too long to be laid out within the first page so that the content of Paragraph 2.1 of Section 2 is divided into halves and the latter half is laid out on a second page.
It is to be noted that, according to the ODA, each layout object class in the generic layout structure has an expression called a structure expression as an attribute "generator for subordinates" (hereinafter referred to as a "GFS") to represent a specific layout structure which can be generated. The structure expression is an expression representative of limitations of a structure immediately subordinate to a layout object belonging to a corresponding layout object class. The structure expression consists of a combination of a term SEQ, AGG, CHO, REP and an object class identifier (hereinafter referred to as a "class ID").
The meaning of each of the terms will be described below.
It is assumed here that "a" and "b" indicate layout objects belonging to classes identified by the class IDs "A" and "B", respectively.
(1) The class ID is a symbol for primarily identifying each class within the generic layout structure.
(2) If a structure expression containing the class ID term is evaluated, one layout object belonging to a layout object class indicated by the class ID is generated as the evaluation result of the class ID term.
(3) If a structure expression containing the term SEQ is evaluated, the evaluation result of terms which follow the term SEQ indicates that the evaluated terms are linked in that order.
For example, the evaluation result of the structure expression (SEQ A B) is (a b).
(4) If a structure expression containing the term AGG is evaluated, the evaluation result of terms which follow the term AGG indicates that the evaluated terms are linked in arbitrary order.
For example, the evaluation result of the structure expression (AGG A B) is (A B) or (b a).
(5) If a structure expression containing the term CHO is evaluated, the evaluation result of terms which follow the term CHO indicates that any one of the evaluated terms is selected.
For example, the evaluation result of the structure expression (CHO A B) is (a) or (b).
(6) If a structure expression containing the term OPT is evaluated, the evaluation result is either an evaluated term which follows the term OPT or nothing.
For example, the evaluation result of the structure expression (OPT A) is (a) or "nothing".
(7) If a structure expression containing the term REP is evaluated, the evaluation result indicates that an evaluated term which follows the term REP is repeated once or an arbitrary number of times more than once.
For example, the evaluation result of the structure expression (REP A) is (a), (a a), (a a a), . . . , or (a a . . . a).
In addition, such a structure expression can be represented as a combination of terms selected from the aforesaid terms, for example, in the form of (SEQ(CHO A B)(OPT C)). The evaluation result of the structure expression (SEQ(CHO A B)(OPT C)) is (a), (a c), (b) or (b c). Each layout object class in the generic layout structure has any of the above-described structure expressions in its GFS.
Regarding the kind of immediately subordinate object which can be linked to a layout object belonging to a certain class, the layout object is limited by the structure expression contained in the GFS of the certain class. In other words, an object corresponding to any of the evaluation results of the structure expression can only be immediately linked to the layout object as a subordinate object. For example, if a layout object class whose class ID is "X" has the structure expression (SEQ(CHO A B)(OPT C)) in its GFS, the object a can be immediately linked to an object x which belongs to the layout object class having the class ID "X", but it is impossible to link both of the objects a and b to the same.
As described above, the generic layout structure is represented by a combination of an operator called a structure generator and a frame class representing the template of an actual frame. FIG. 8 shows one example of the generic layout structure, and FIG. 9 shows a layout image represented by the generic layout structure.
As a related art concerning document processing (hereinafter referred as "layout processing") which utilizes a generic structure and a specific structure to generate a specific layout structure on the basis of a document content and a generic layout structure, there is a method of sequentially generating the specific layout structure by sequentially trying a plurality of choices related to structure generation which are described in the generic layout structure. In such a method, a desired part of a document content is laid out in accordance with one choice selected from among the choices in a predetermined order. Layout processing is achieved, for example, by performing sequential selection from the plurality of choices related to the structure generation of each class on the basis of left-depth-first-search.
FIG. 11(a) shows one example of a specific layout structure corresponding to the generic layout structure shown in FIG. 10. The shown specific layout structure is obtained by performing selection from the choices of the generic layout structure on the basis of left-depth-first-search.
It is assumed here that a, b, c, d, e and f respectively denote layout objects belonging to individual object classes whose class IDs are R, A, B, C, D, E and F. Since the object classes individually serve as choices, they are hereinafter referred to as choices R, A, B, C, D, E and F, respectively.
When the specific layout structure (refer to FIG. 11(a)) is generated, information is stored into a stack which information indicates that a certain layout object class was selected at the time when a particular choice among the plurality of choices was processed. FIG. 11(b) shows the content of the stack obtained when the specific layout structure shown in FIG. 11(a) is generated. In FIG. 11(b), "A", "C","B" and "E" respectively denote information indicating that the choices A, C, B and E have been selected.
If the layout fails, the next choice is selected in a predetermined order (the uppermost information in the stack shown in FIG. 11(b) is restored and another choice is selected), thereby again carrying out layout processing. At this time, to cancel the specific layout structure generated according to the immediately previous choice, generation and deletion of layout objects are performed so as to match the state of the layout to the new choice.
In the above-described conventional layout method, however, when the specific layout structure is generated, the information must be stored into the stack which information indicates that the certain layout object class was selected at the time when the particular choice among the plurality of choices was processed. If the layout fails, it is necessary to perform a retry of a new layout by restoring the uppermost information in the stack and selecting another choice.
The following description is made of a retry of layout which is performed when the layout of the choice C has failed, for example, in the specific layout structure shown in FIG. 11(a).
The state of the stack before the retry is as shown in FIG. 11(b). Therefore, the uppermost information "E" is first obtained, then the stack is restored to the state wherein it was placed before the choice E was laid out, on the basis of the information "E", and then the choice F is selected instead of the choice E, whereby a new specific layout structure can be obtained. FIG. 12(a) shows the specific layout structure obtained by performing such a retry. FIG. 12(b) shows the state of the stack obtained by performing the retry. In FIG. 12(b), "F" represents information indicating that the choice F has been selected. In this case as well, however, the layout fails since an alternative candidate (the choice D) for the choice C has not been selected.
Subsequently, the uppermost information "F" is obtained by further making reference to the content of the stack shown in FIG. 12(b), then the stack is restored to the state wherein it was placed before the choice F was laid out, on the basis of the information "F" (in this case, the stack is restored to the state wherein it was placed when the choice A was laid out, due to limitations of the generic layout structure) and then the choice D is selected instead of the choice C, whereby a new specific layout structure can be obtained. FIG. 12(c) shows the specific layout structure obtained by performing such a retry. FIG. 12(d) shows the state of the stack obtained by performing the retry. In FIG. 12(d), "D" represents information indicating that the choice D has been selected.
As is apparent from the foregoing description, according to the conventional layout method, to cancel a specific layout structure generated according to an immediately previous choice, it is necessary to frequently perform generation and deletion of layout objects so as to match the state of a layout to a new choice. As a result, it is difficult to achieve layout processing with high efficiency.